|
A straight-line grammar (sometimes with "straight-line" in scare quotes,〔http://www.almob.org/content/1/1/4〕 also abbreviated as SLG) is a formal grammar that generates exactly one string.〔Florian Benz and Timo Kötzing, “An effective heuristic for the smallest grammar problem,” Proceeding of the fifteenth annual conference on Genetic and evolutionary computation conference - GECCO ’13, 2013. ISBN 978-1-4503-1963-8 , p. 488〕 Consequently, it does not branch (every non-terminal has only one associated production rule) nor loop (if non-terminal ''A'' appears in a derivation of ''B'', then ''B'' does not appear in a derivation of ''A'').〔 SLGs are of interest in fields like Kolmogorov complexity, Lossless data compression, Structure discovery and Compressed data structures. The problem of finding an SLG of minimal size that generates a given string is called the Smallest grammar problem. ==Formal Definition== A context-free grammar ''G'' is an SLG if: 1. for every non-terminal ''N'', there is at most one production rule that has ''N'' as its left-hand side, and 2. the graph ''G''=<''V'',''E''>, defined by ''V'' being the set of non-terminals and (''A'',''B'') ∈ ''E'' whenever ''B'' appears at the right-hand side of a production rule for ''A'', is acyclic.〔 Here: p.215, Sect.2〕 An SLG in Chomsky normal form is equivalent to a straight-line program. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Straight-line grammar」の詳細全文を読む スポンサード リンク
|